//
//  main.c
//  007--去掉重复字母
//
//  Created by Shawn Li on 2020/5/13.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 题目:• 去除重复字母(LeetCode-困难)
 给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）
 示例1:
 输入:"bcabc"
 输出:"abc"
 
 示例2:
 输入:"cbacdcbc"
 输出:"acdb"
 */

/*
 解题关键:
 字典序: 字符串之间比较和数字比较不一样; 字符串比较是从头往后挨个字符比较,那个字符串大取决于两个字符串中 【第一个对应不相等】 的字符; 例如 任意一个a开头的字符串都大于任意一个b开头的字符串;例如字典中apple 大于 book;
 题目的意思,你去除重复字母后,需要按最小的字典序返回.并且不能打乱其他字母的相对位置;
 例如 bcabc 你应该返回abc, 而不是bca,cab;
 例如 cbacdcbc 应该返回acdb,而不是cbad,bacd,adcb
 例如 zab,应该返回zab,而不是abz;
 
 思路：
 1. s 为空或者长度为 1，需要特殊判断。
 2. record 数组记录字母出现的次数。
 3. stack 堆栈，用以存储结果和虚招次序。
 4. 遍历字符串 s; 当前字符记为 keyChar ,
 5. 判断 0 ~ top 中是否有有 keyChar，
 6. 若已经存在了；record 中该字符的次数若是 > 1 那么需要将次数-1，若次数 = 1，那么说明keyChar 是最后一次了，那么不能出栈了。
 7. 若不存在；那么说明这是这个字符最后一次出现了，那么将所有字典序比 keyChar 大的并且后面还会出现的字符全部出栈，再将 kayChar 入栈，这时的位置就是 keyChar 的正确位置。
        条件为：top > -1 && 字典序比 keyChar 大 && 后面还会出现的字符(次数>1)
 8. top++ keyChar 入栈。
 
 */
char * removeLetters(char *s){
    int len = (int)strlen(s);
    
//    先处理特殊情况
    if (s == NULL || len == 0) {
        return "";
    }
    
    if (len == 1) {
        return s;
    }
    
//    标记数组统计所有字符是否出现了。
    char record[26] = {0};
//    为了完成字典序的限制，需要使用堆栈。多一个位置以便最后放结尾标志
    char *stack = (char*)malloc((len + 1) *sizeof(char));
    
//    memset 将 stack 中 规定长度内的空间都填充为 0。
    memset(stack, 0, (len + 1) * sizeof(char));
    
    int top = -1;
    
//    统计每个字符的频次
    for (int i = 0; i < len; i++) {
         record[s[i] - 'a']++;
    }
    
//    为了完成字典序的限制，需要使用堆栈。
    for (int i = 0; i < len; i++) {
//        标记堆栈中是否已经存在该字符
        int isExist = 0;
        for (int j = 0; j <= top; j++) {
            if (s[i] == stack[j]) {
                isExist = 1;
                break;
            }
        }
//        如果存在的话，那么说明该字符已经入栈了，这一次就不入了，同时 标记次数 要减一
        if (isExist == 1) {
            record[s[i] - 'a']--;
        } else {
//            如果不存在，那么当前字符就要入栈了
//            入栈的时候，如果 栈顶有字符 而且 栈顶字符的字典序比当前字符还大 而且 栈顶字符后面还会出现，
//            那么就让栈顶字符把位置让出来给当前字符，因为这样可以让整个字符的字典序更小。
//            所以将符合上述条件的字符全部出栈，同时这些字符的 标记次数 要减一。
            while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
                record[stack[top] - 'a']--;
//                弹栈
                top--;
            }
            
            top++;
//            压栈，这个位置就是当前字符的正确位置
            stack[top] = s[i];
        }
    
    }
//    在结尾补上一个结束标记
    stack[++top] = '\0';
    
    return stack;
}



int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    printf("去掉重复字母! LeetCode-困难 \n");
       
    char *s ;
    s = removeLetters("bcabc");
    printf("%s\n",s);

    s = removeLetters("zab");
    printf("%s\n",s);

    s = removeLetters("cbacdcbc");
    printf("%s\n",s);

    printf("\n");
    
    return 0;
}
